The following is based on Korean Patent Application No. 99-23948 filed Jun. 24, 1999, herein incorporated by reference.
1. Field of the Invention
The present invention relates to an image segmenting apparatus and method, and more particularly, to an image segmenting apparatus and method for segmenting an object region having the same color in an image which is input through a camera sensor or a video image, or extracting a significant image region from the image.
2. Description of the Related Art
Generally, an image is composed of three color signals; Red, Green and Blue (R, G, B). Image segmenting operation extracts same color regions or same object regions from an image which is composed of input color signals. The extracted image data can be utilized in fields related to digital image processing such as image analysis, image compression or image recognition for object-based image information processing or automation application. Most of the image segmenting methods based on color signals usually project input color signals onto different types of color spaces and then extract density in each color space, or segment an image taking into account local adjacency of color pixels in an image region. A problem with these conventional image segmenting methods is that objects which are the same or objects having the same color do not show the same color characteristic in an image input through a camera or the like due to complexity, which appears under various environments and conditions related to image formation, and the limit of the image segmenting methods. This problem of the color characteristic causes an excessively large number of noise regions during image segmentation. The color characteristic or brightness characteristic is completely different from or sufficiently deviates from the color characteristic of an original object.
To solve these problems, R. Schettini (xe2x80x9cPattern Recognition Letterxe2x80x9d, 14, 1993) and R. Beveridge (xe2x80x9cIJCVxe2x80x9d, 2, 1989) removes noise regions, which are generated after initial image segmentation, using color information included in each segment. In this method, a distance between adjacent regions is measured in a color space based on a Eucledian distance or a probabilistic distance, and adjacent regions having smaller color difference from each other are merged into one. However, the method has the following problems.
1. Even if two adjacent regions are segmented from the same object or the same color region in an image, frequently, it is difficult to combine the two adjacent image regions due to lack of similarity between them.
2. Results of sequential combination of adjacent image regions vary according to the order in which the regions are combined.
3. Combination evaluation must be performed with respect to every adjacent region.
4. Information on the importance or size of each region obtained from initial image segmentation, or information on the structural inclusive relations among regions in an image, cannot completely be used.
Illumination, shapes of objects, the objects"" mutual geometric arrangement, and mutual position between an observer or an image input apparatus and the objects, are the important components forming an image. Ideal image segmentation is, in spite of these various conditions of image formation, to effectively distinguish significant objects or the same color regions from a background or other objects in a similar manner to human recognition. Generally, for the same objects, or for backgrounds or objects having the same color, shade or shadow regions may occur due to a variety of objects"" mutual spatial arrangements and the shapes of objects themselves. The shade or shadow regions are main causes which make image segmentation difficult. In other words, when performing image segmentation using color or brightness distribution information, the shade or shadow regions are extracted as independent regions because each of the shade or shadow regions has an independent color characteristic and brightness distribution. When the extracted shade or shadow regions are removed during the image segmentation, separation of significant objects from the image is greatly influenced by the removal, making the segmenting operation difficult. For example, when the shade regions are removed by using similarity of color information between adjacent object regions in a color space, it is difficult to effectively combine adjacent regions by using only the similarity of color information. Because the color information in the shade regions disappears due to the decline in overall color intensity or consistency of the color information disappears due to image noise. In this case, geometrical information including edge information between regions, or topological information including mutual relationship in arrangement and a degree of adjacency, is utilized.
As pointed out by R. Schettini, there is a method of combining regions by post-processing after initial segmentation, using a region adjacent graph (RAG) (Matas, Int. Conf. on Computer Vision, 1995), which is a graph showing the condition of adjacency between image regions. However, it is difficult to determine an order in combining adjacent regions having similar characteristics, based on only the adjacency condition which has a horizontal structure. For example, when representing relations between regions generated after initial segmentation by a RAG, binary graphs composed of nodes indicating the regions and branches connecting nodes of adjacent regions are generated. Each of the binary graphs has a horizontal structure in which each branch is non-directional. When a region has a plurality of adjacent regions, it is preferable to determine which adjacent region is combined with the region. Even if a region Ri has the most similar color characteristic to a region Rj, and thus the region Ri, is combined with the region Rj, and even if the region Rj, is combined with a region Rk which has the most similar color characteristic to the region Rj, the region Ri and the region Rk may have different color characteristics. Different combination order may cause completely different results of segmentation. Accordingly, it may be difficult to combine adjacent regions sequentially into one.
To solve the above problems, Rosenfeld (xe2x80x9cDigital Picture Processingxe2x80x9d, Academic Press, 1982) improves an ordering method for combining adjacent regions by repeating a step of combining the most similar two regions among adjacent regions into one and reconstructing a RAG. However, the method also has problems caused by a graph having a horizontal structure. In addition, since there is no information on the importance of adjacent regions when combining adjacent regions based on a RAG, the same combination test and evaluation need to be simultaneously performed with respect to every adjacent region.
To solve the above problems, it is an objective of the present invention to provide an image segmenting apparatus and method for deriving a hierarchical region structure between regions from a result of initial image segmentation, rearranging the order in which regions are combined and determining hierarchical inclusive relation using the hierarchical region structure so as to find noise regions, and removing the noise regions.
Accordingly, to achieve the above objective, there is provided an image segmenting apparatus includes an initial image segmenting unit, a region structurizing unit and a redundant region combiner. The initial image segmenting unit converts color signals of an input image into a predetermined space, and segments the input image into a plurality of regions according to positions of color pixels of the input image in the color space. The region structurizing unit classifies the plurality of regions into layers according to horizontal, adjacent relation and hierarchical, inclusive relation between the regions, and groups adjacent regions into region groups in each layer, so as to derive a hierarchical, inclusive relation between the region groups. The redundant region combiner determines the order in which adjacent regions are combined according to the horizontal, adjacent relation between regions and the hierarchical, inclusive relation between region groups. The redundant region combiner also determines whether to combine adjacent regions according to the determined combination order, and combines adjacent regions if the adjacent regions are determined to have substantially the same image property.
There is also provided an image segmenting method including an initial image segmenting step and a post processing step. In the initial image segmenting step, color signals of an input image are converted into a predetermined color space and the input image is segmented into a plurality of regions according to positions of color pixels of the input image in the color space. In the post processing step, the plurality of regions are classified into layers according to the horizontal, adjacent relation and hierarchical, inclusive relation between the regions. Adjacent regions are grouped into region groups in each layer, so as to the derive hierarchical, inclusive relation between the region groups, determining the order in which adjacent regions are combined and whether to combine two adjacent regions. Adjacent regions are combined if the adjacent regions are determined to have substantially the same image property.